1. Field of the Invention
The present invention relates to local area networks and, in particular, to a partitioning port state machine for a repeater interface controller that connects segments of a bus/tree network.
2. Discussion of the Prior Art
A local area network, or LAN, is a communications system that provides interconnection among a number of independent computing stations within a small area, such as a single building or a group of adjacent buildings.
William Stallings' overview of local area network concepts and technology, as set forth in (1) Local Area Networks, Third Edition, MacMillan Publishing Co., and (2) Handbook of Computer-Communications Standards, Volume 2, Howard W. Sams Publishing, provides the basis for the following background discussion.
As discussed by Stallings, in the context of a communications network, the term "topology" refers to the way in which the stations comprising the network are interconnected.
The most-commonly implemented local area network topology is the so-called "bus/tree" topology.
In a "bus" network, all stations attach directly to a linear transmission medium, or bus, through appropriate hardware interfacing. A transmission from any station in the network propagates the length of the medium and can be received by all other stations.
A "tree" topology is a generalization of the bus topology. In a tree network, the transmission medium is a branching cable with no closed loops. Each branch defines a network "segment". As in a bus network, a transmission from any station in the network propagates through the medium on all segments and can be received by all other stations.
Data are transmitted in a bus/tree network in units that are usually referred to as "frames" or "packets". In addition to data to be transmitted, each packet includes control information such as the address of the packet source (transmit station) and the address of the packet destination (receive station).
Because all stations of a bus/tree network share a common transmission medium, only one station may transmit at a time. A transmitted packet propagates through the medium, is received by all stations on the network and is copied by the destination station to which it is addressed.
Bus/tree networks utilize one of two types of data transmission techniques: baseband or broadband. Baseband transmission uses digital signalling and can be implemented with either twisted pair or coaxial cable. Broadband transmission uses analog signalling in the radio-frequency (RF) range and is implemented with coaxial cable.
In a baseband LAN, digital signals are transmitted onto the medium as voltage pulses, usually utilizing Manchester encoding. Transmission is bidirectional; that is, a signal inserted at any point on the medium propagates in both directions to the ends of the medium where it is absorbed. Baseband systems can extend only a limited distance, usually about 1 km. maximum, because of attenuation of the digital signal.
Because of the wide variety of physical, electrical and procedural characteristics available to designers of equipment for local area networks, it has become widely acknowledged that certain standards must be observed. For example, the International Organization for Standardization (ISO) has developed a voluntary Open Systems Interconnection (OSI) model which defines a general computer system architecture. An "open" system may be implemented in any way provided that it conforms to a minimal set of OSI standards that allow it to communicate with other "open" systems.
A number of local area network protocol standards have been developed by the Institute of Electrical and Electronics Engineers (IEEE) 802 committee One of these standards, the IEEE 802.3 standard, defines a protocol for a bus/tree local area network. As discussed below, the IEEE 802.3 standard defines a bus/tree protocol that implements the carrier sense multiple access with a collision detection (CSMA/CD. The standard also defines a media access control (MAC) function for transmitting packets to and receiving packets from the transmission medium as well as packet structure and the interaction that takes place between MAC entities in the network.
The IEEE 802.3 standard anticipates that stations will be located only a short distance from the physical transmission medium. Thus, the standard specifies a medium attachment unit (MAU) that connects directly to the physical medium and an attachment unit interface (AUI) which serves as the transmission medium between a station and an associated MAU.
As stated above, in a bus/tree network, a transmission from any station in the network propagates through the medium on all segments and can be received by all other stations. Thus, the 802.3 CSMA/CD protocol defines a "random access" or "contention" technique for addressing the problem of how multiple stations will share a common transmission medium when all stations transmit randomly and contend with one another for transmission time on the network.
According to the well-known carrier sense multiple access (CSMA) technique, a station wishing to transmit first listens to the medium to determine if another transmission is occurring. If the medium is in use, then the station idles for some pseudorandom time and then re-attempts the transmission. If the medium is idle, then the station transmits. If two or more stations transmit at the same time, then a collision occurs. To account for collisions, the transmitting station waits a period of time after transmitting for an acknowledgment that its transmission has been received by the destination station. If no acknowledgement is received, then the station assumes that a collision has occurred and retransmits.
Although the CSMA technique is an efficient method for managing transmission in a bus/tree network, it does have deficiencies. For example, when two packets collide, the medium remains unstable for the duration of transmission of both packets. For long packets, the amount of bandwidth wasted before re-transmission is permitted can be considerable.
This bandwidth waste can be reduced if a station continues to listen to the medium while it is transmitting. The rules for this procedure, known as carrier sense multiple access with collision detection (CSMA/CD) are as follows. If a station wishing to transmit senses that the medium is idle, then it transmits. If the station senses that the medium is busy, it continues to listen to the medium until it senses that the medium is idle and then immediately transmits. If the station detects a collision during transmission, then it transmits a brief jamming signal to assure that all stations on the network know that there has been a collision; then it ceases transmission. After transmitting the jamming signal, the station waits a pseudo-random period of time and then re-attempts the transmission.
The length of a bus/tree network can be extended by connecting together a number of medium "segments" using "repeaters". A "repeater" comprises two or more MAUs and associated logic joined together and connected to two or more different segments of the network medium by corresponding AUIs. The repeater passes retimed digital signals in both directions between the two segments, amplifying and regenerating the signals as they pass through.
A conventional repeater is transparent to the rest of the network system. It does no buffering and does not isolate one segment from the rest of the network. Thus, if two stations on different segments attempt transmission at the same time, their transmissions will collide.
The IEEE 802.3 standard provides for a variety of medium and data-rate options within the protocol. To distinguish implementations using different alternatives, the following notation has been adopted: EQU (data rate,Mbps)(medium type)(max. segment lgth*100 m)
Thus, an IEEE 802.3 network with a data rate of 10-Mbps, a baseband medium and a maximum segment length of 500 meters is referred to as a 10BASE5 network.
The IEEE 802.3 10BASE5 standard specifies use of a 50-ohm coaxial cable as the transmission medium and a data rate of 10 Mbps using digital signalling with Manchester encoding. These parameters define the maximum cable length at 500 m./segment.
The IEEE 802.3 10BASE2 standard provides a lower-cost network configuration well suited for personal computer networks and commonly-referred to as "Cheapernet". As with a 10BASE5 network, a 10BASE2 network uses 50-ohm coaxial cable and Manchester encoding at a data rate of 10 Mbps.
The difference between a 10BASE5 and a 10BASE2 Cheapernet network is the use in a Cheapernet network of a thinner, more flexible cable which enables expended, simpler installation options. However, the thinner cable suffers greater signal attenuation and lower noise resistance and, thus, supports fewer stations over shorter segment lengths.
One of the best known local area networks is Ethernet, which was developed by Xerox Corporation in the mid-1970s. The Ethernet architecture was used as the basis for an IEEE 802.3 network which includes several features worthy of notation. The IEEE 802.3 network includes a "heartbeat" function. This is a signal sent from the MAU to the station that confirms that the MAU collision signal circuitry is working and connected to the station. Without this signal, which is referred to as the signal-quality-error signal, the station is unsure whether the frame was actually sent without a collision or whether a defective MAU failed to properly report a collision. IEEE 802.3 also includes a jabber function. This is a self-interrupt capability that allows a MAU to inhibit transmitted data from reaching the medium if the transmission occurs for longer than a predetermined time period.
One version of an IEEE 802.3 network, 10BASE-T Ethernet, uses installed twisted pair "telephone wiring" to provide point-to-point links, compared to the bus based architecture of other Ethernet baseband networks. While providing a relatively cheap medium, a 10BASE-T network requires separate transmit and receive pairs. This gives rise to installations problems which, as discussed below, may be partially solved by the specification's link detection function.
FIG. 1 shows an example of an Ethernet 802.3 network topology that implements a number of the LAN concepts discussed above. FIG. 1 shows a repeater A that connects two "Thick Ethernet" 10BASE5 segments. Repeater B connects the left-hand 10BASE5 segment with three 10BASE2 Cheapernet segments. Repeater C connects the right-hand 1 10BASE5 segment to two 10BASE2 Cheapernet segments. Repeater D connects the 10BASE5 segment to two 10BASE-T Ethernet stations in a point-to-point configuration.
As stated above, use of "dual" twisted pair telephone wire in a 10BASE-T Ethernet system increases the likelihood of stations being improperly connected to the network.
FIG. 2 shows a proper twisted pair link. That is, a "cross-over" is utilized to connect the transmit port of the left-hand MAU to the receive port of the right-hand MAU. Similarly, the cross-over connects the transmit port of the right-hand MAU to the receive port of the left-hand MAU.
As shown in FIG. 3, the 10BASE-T Ethernet standard defines a mechanism for confirming a proper twisted pair link. During the IDLE state, each MAU in the network transmits a series of "link pulses" and monitors its receive pair of cables for reception of link pulses which are fed back to the transmitting station by its repeater. If the transmitting station detects seven consecutive link pulses at its receive port, then a proper twisted pair link is confirmed and the station transmits the data packet.
Chapter 9 of the IEEE 802.3 specification defines the standard for a repeater utilizable in 10 Mbps baseband networks. As stated in the specification, network segments may be connected directly by repeater combinations as long as only one signal path is operative between any two points on the network and the number of repeaters in that signal path is not greater than four. The 802.3 repeater must be designed to receive and decode data from any network segment under defined jitter conditions and to retransmit data to all other network segments attached to it with timing and amplitude restored. Retransmission of data occurs simultaneously with reception. If a collision occurs, the repeater propagates the collision event throughout the network by transmitting a jam signal. The repeater also detects and isolates faulty network segments.
FIG. 4 shows an example of an 802.3 multi-port repeater system 1. A Manchester encoded data packet received by one of multiple transceivers (XCVR) 2 of the system 1 is processed by the associated port logic 3 and then provided via a multiplexor 4 to a decoder 5. The decoder 5 recovers NRZ data and a clock signal from the Manchester encoded input. Data is placed on a CONTROL BUS for processing by a central state machine 6, which implements the repeater's protocol facilities, aided by a set of central counters 7. Information generated by the port state machine 6 may be provided to a set of display devices and drivers 8. Recovered data from the decoder 5 is entered via an RX DATA PATH BUS to an elasticity buffer FIFO 9 from which it is read, Manchester encoded and retransmitted to all network segments via transceivers 2.
The IEEE 802.3 committee's Hub Management Task Force currently has under consideration a Draft Supplement to the IEEE 802.3 standard relating to hub management. The goal of the hub management standard is to provide Management Information Service (MIS) capability over the network. Since repeaters enjoy a "privileged" view of transmissions on an 802.3 network, they are a logical place to implement the MIS function.
The draft standard describes management of repeater hubs in terms of a general model of management of resources within the OSI environment.